package org.example.dynamic_planning;

public class The_largest_subarray_sum {
    public static void main(String[] args) {
        //最大子数组和

        //给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
        //子数组
        //是数组中的一个连续部分。
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        int i = maxSubArray(nums);
        System.out.println(i);
    }
    public static int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i],nums[i]+dp[i-1]);
            max = Math.max(max,dp[i]);
        }
        return Math.max(max, dp[0]);
    }
}
